package niuke;

import java.util.Scanner;

public class DPsier {

    // 注意类名必须为 Main, 不要有任何 package xxx 信息
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n=in.nextInt();
            int V=in.nextInt();
            int[] v=new int[n+1];
            int[] w=new int[n+1];
            for(int i=1;i<=n;i++){
                v[i]=in.nextInt();
                w[i]=in.nextInt();
            }
            int unfilled=unfilled(n,V,v,w);
            int filled=filled(n,V,v,w);
            System.out.println(unfilled);
            System.out.println(filled);
            in.close();
        }
        public static int unfilled(int n,int V,int[] v,int[] w){
            int[] f=new int[V+1];
            for(int i=1;i<n+1;i++){
                for(int j=0;j<=V;j++){
                    if(j-v[i]>=0){
                        f[j]=Math.max(f[j],f[j-v[i]]+w[i]);
                    }
                }
            }
            return f[V];
        }
        public static int filled(int n,int V,int[] v,int[] w){
            int[] f=new int[V+1];
            for(int j=1;j<=V;j++){
                f[j]=-1;
            }
            for(int i=1;i<n+1;i++){
                for(int j=0;j<=V;j++){

                    if(j-v[i]>=0&&f[j-v[i]]!=-1){
                        f[j]=Math.max(f[j],f[j-v[i]]+w[i]);
                    }
                }
            }
            return f[V]==-1?0:f[V];
        }

}
